Sum of Divisors
Introduction
- Many questions in number theory begin with a simple idea:
What numbers divide a given number? - From this idea grows a powerful tool: the sum‑of‑divisors function, written $\sigma(n)$.
- This chapter introduces:
- What divisors are
- How to find them
- How to add them
- Why the function $\sigma(n)$ is so important
What Are Divisors?
- A divisor (or factor) of a number $n$ is a whole number that divides $n$ with no remainder.
- Examples:
- Divisors of $6$: $1, 2, 3, 6$
- Divisors of $12$: $1, 2, 3, 4, 6, 12$
- Key ideas:
- Every positive integer has at least two divisors: $1$ and itself.
- Divisors come in pairs:
- For $12$, the pairs are $(1,12)$, $(2,6)$, $(3,4)$.
Finding Divisors of a Number
A simple method:
- Start at $1$ and test each whole number up to $n$.
- If it divides evenly, record it.
- Stop when you reach $n$.
A more efficient method:
- You only need to test numbers up to $\sqrt{n}$.
- For each divisor $d$ you find, you automatically know its partner $n/d$.
Example for $36$:
- Test $1$ through $6$ (since $\sqrt{36} = 6$).
- Divisors found:
- $1$ and $36$
- $2$ and $18$
- $3$ and $12$
- $4$ and $9$
- $6$ and $6$ (a repeated pair)
- Full list: $1,2,3,4,6,9,12,18,36$
Patterns in Divisors
Some useful observations:
- Odd numbers can only have odd divisors.
- Prime numbers have exactly two divisors: $1$ and the number itself.
- Perfect squares have an odd number of divisors (because one pair repeats).
- Numbers with many small prime factors tend to have many divisors.
These patterns help us predict divisor behavior without listing everything.
Adding Up Divisors: First Examples
Let’s add all the divisors of a number.
- For $6$:
Divisors: $1,2,3,6$
Sum: $1+2+3+6 = 12$ - For $10$:
Divisors: $1,2,5,10$
Sum: $1+2+5+10 = 18$ - For $12$:
Divisors: $1,2,3,4,6,12$
Sum: $1+2+3+4+6+12 = 28$
This process leads naturally to a function that captures this idea.
Defining the Sum‑of‑Divisors Function, $\sigma(n)$
- The sum‑of‑divisors function is written $\sigma(n)$.
- $\sigma$ is the Greek letter sigma.
- It means:
Add up all positive divisors of $n$.
Examples:
- $\sigma(6) = 12$
- $\sigma(10) = 18$
- $\sigma(12) = 28$
A formal definition: $$\sigma(n) = \sum_{\substack{d \mid n}} d$$ This means “add all $d$ such that $d$ divides $n$.”
Redefining $\sigma(n)$ using prime factorization
The formula for $\sigma(n)$ becomes especially nice when we use the prime factorization of $n$.
If $$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k},$$ then $$\sigma(n) = (1 + p_1 + p_1^2 + \cdots + p_1^{a_1}) \cdots (1 + p_k + p_k^2 + \cdots + p_k^{a_k}).$$ Why this works (intuitively):
- Every divisor of $n$ is formed by choosing:
- a power of $p_1$ between $p_1^0$ and $p_1^{a_1}$,
- a power of $p_2$ between $p_2^0$ and $p_2^{a_2}$,
- and so on.
- The formula simply adds up all possible combinations.
Example:
- $n = 12 = 2^2 \cdot 3^1$
- Then: $$\sigma(12) = (1 + 2 + 4)(1 + 3) = 7 \cdot 4 = 28.$$
Matches our earlier calculation.
Properties of $\sigma(n)$
Some helpful facts:
- Multiplicative property:
If $a$ and $b$ share no prime factors, then $$\sigma(ab) = \sigma(a)\sigma(b).$$ - For primes:
If $p$ is prime, $$\sigma(p) = 1 + p.$$ - For prime powers: $$\sigma(p^k) = 1 + p + p^2 + \cdots + p^k.$$
- Growth:
$\sigma(n)$ is usually larger than $n$, but not always by much.
Prime Numbers and $\sigma(n)$
- If $p$ is prime:
- Divisors: $1$ and $p$
- So $\sigma(p) = p + 1$
- For a prime power $p^k$:
- Divisors: $1, p, p^2, \dots, p^k$
- Sum is a geometric series
This makes primes and prime powers especially easy to work with.
Perfect, Abundant, and Deficient Numbers
These classifications compare $\sigma(n)$ to $n$ itself.
- Perfect numbers:
$\sigma(n) = 2n$
(Equivalently: the sum of proper divisors equals $n$.)
Example: $6$ and $28$. - Abundant numbers:
$\sigma(n) > 2n$
Example: $12$. - Deficient numbers:
$\sigma(n) < 2n$
Example: $10$.
These categories reveal interesting structure in the integers.
Why $\sigma(n)$ Matters in Number Theory
- It connects divisors, primes, and factorization.
- It helps classify numbers (perfect, abundant, deficient).
- It appears in:
- the study of integer partitions
- modular forms
- the Riemann zeta function
- many unsolved problems in mathematics
- Despite its simple definition, $\sigma(n)$ leads to deep questions.
Calculator
divisors(n)
- Returns a list of all positive divisors of $n$.
divisors(12) divisors(18)
sumDivisors(n)
- Returns the sum of all positive divisors of $n$ (the function $\sigma(n)$).
sumDivisors(12) sumDivisors(18)
sumProperDivisors(n)
- Returns the sum of all proper divisors of $n$ (all divisors except $n$ itself).
sumProperDivisors(12) sumProperDivisors(18)
numDivisors(n)
- Returns the number of positive divisors of $n$.
numDivisors(12) numDivisors(18)
Exercises
- List all divisors of $18$ and compute $\sigma(18)$.
- Compute $\sigma(25)$ using both:
- direct listing
- the prime‑power formula
- Determine whether $20$ is perfect, abundant, or deficient.
- Compute $\sigma(2^4)$.
- Find $\sigma(45)$ using prime factorization.
- True or false: If $p$ is prime, then $\sigma(p^2) = 1 + p + p^2$.
- Compute $\sigma(28)$ and verify that $28$ is a perfect number.
- Find all divisors of $30$ and classify $30$ as perfect, abundant, or deficient.